SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Metropolis–Hastings algorithm</title>

</head>

Metropolis–Hastings algorithm

</h1>

</header>

In <a href="Statistics" title="Statistics">statistics</a> and <a href="Statistical_physics" class="mw-redirect" title="Statistical physics">statistical physics</a>, the Metropolis–Hastings algorithm is a <a href="Markov_chain_Monte_Carlo" title="Markov chain Monte Carlo">Markov chain Monte Carlo</a> (MCMC) method for obtaining a sequence of <a href="Pseudo-random_number_sampling" class="mw-redirect" title="Pseudo-random number sampling">random samples</a> from a <a href="Probability_distribution" title="Probability distribution">probability distribution</a> from which direct sampling is difficult. New samples are added to the sequence in two steps: first a new sample is proposed based on the previous sample, then the proposed sample is either added to the sequence or rejected depending on the value of the probability distribution at that point. The resulting sequence can be used to approximate the distribution (e.g. to generate a <a href="Histogram" title="Histogram">histogram</a>) or to <a href="Monte_Carlo_integration" title="Monte Carlo integration">compute an integral</a> (e.g. an <a href="Expected_value" title="Expected value">expected value</a>).

Metropolis–Hastings and other MCMC algorithms are generally used for sampling from multi-dimensional distributions, especially when the number of dimensions is high. For single-dimensional distributions, there are usually other methods (e.g. <a href="Adaptive_rejection_sampling" class="mw-redirect" title="Adaptive rejection sampling">adaptive rejection sampling</a>) that can directly return independent samples from the distribution, and these are free from the problem of <a href="Autocorrelation" title="Autocorrelation">autocorrelated</a> samples that is inherent in MCMC methods.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The algorithm is named in part for <a href="Nicholas_Metropolis" title="Nicholas Metropolis">Nicholas Metropolis</a>, the first coauthor of a 1953 paper, entitled <a href="Equation_of_State_Calculations_by_Fast_Computing_Machines" title="Equation of State Calculations by Fast Computing Machines">Equation of State Calculations by Fast Computing Machines</a>, with <a href="Arianna_W._Rosenbluth" title="Arianna W. Rosenbluth">Arianna W. Rosenbluth</a>, <a href="Marshall_Rosenbluth" title="Marshall Rosenbluth">Marshall Rosenbluth</a>, <a href="Augusta_H._Teller" title="Augusta H. Teller">Augusta H. Teller</a> and <a href="Edward_Teller" title="Edward Teller">Edward Teller</a>. For many years the algorithm was known simply as the Metropolis algorithm.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a> The paper proposed the algorithm for the case of symmetrical proposal distributions, but in 1970, <a href="W.K._Hastings" class="mw-redirect" title="W.K. Hastings">W.K. Hastings</a> extended it to the more general case.<a href="#cite_note-Hastings-3">[3]</a> The generalized method was eventually identified by both names, although the first use of the term "Metropolis-Hastings algorithm" is unclear.

Some controversy exists with regard to credit for development of the Metropolis algorithm. Metropolis, who was familiar with the computational aspects of the method, had coined the term "Monte Carlo" in an earlier article with <a href="Stanis%C5%82aw_Ulam" title="Stanisław Ulam">Stanisław Ulam</a>, and led the group in the Theoretical Division that designed and built the <a href="MANIAC_I" title="MANIAC I">MANIAC I</a> computer used in the experiments in 1952. However, prior to 2003 there was no detailed account of the algorithm's development. Shortly before his death, <a href="Marshall_Rosenbluth" title="Marshall Rosenbluth">Marshall Rosenbluth</a> attended a 2003 conference at LANL marking the 50th anniversary of the 1953 publication. At this conference, Rosenbluth described the algorithm and its development in a presentation titled "Genesis of the Monte Carlo Algorithm for Statistical Mechanics".<a href="#cite_note-Rosenbluth-4">[4]</a> Further historical clarification is made by Gubernatis in a 2005 journal article<a href="#cite_note-Gubernatis-5">[5]</a> recounting the 50th anniversary conference. Rosenbluth makes it clear that he and his wife Arianna did the work, and that Metropolis played no role in the development other than providing computer time.

This contradicts an account by Edward Teller, who states in his memoirs that the five authors of the 1953 article worked together for "days (and nights)".<a href="#cite_note-Teller-6">[6]</a> In contrast, the detailed account by Rosenbluth credits Teller with a crucial but early suggestion to "take advantage of <a href="Statistical_mechanics" title="Statistical mechanics">statistical mechanics</a> and take ensemble averages instead of following detailed <a href="Kinematics" title="Kinematics">kinematics</a>". This, says Rosenbluth, started him thinking about the generalized Monte Carlo approach – a topic which he says he had discussed often with <a href="John_von_Neumann" title="John von Neumann">John Von Neumann</a>. Arianna Rosenbluth recounted (to Gubernatis in 2003) that Augusta Teller started the computer work, but that Arianna herself took it over and wrote the code from scratch. In an oral history recorded shortly before his death,<a href="#cite_note-Barth-7">[7]</a> Rosenbluth again credits Teller with posing the original problem, himself with solving it, and Arianna with programming the computer.

<div class="mw-heading mw-heading2"><h2 id="Description">Description</h2></div>

The Metropolis–Hastings algorithm can draw samples from any <a href="Probability_distribution" title="Probability distribution">probability distribution</a> with <a href="Probability_density" class="mw-redirect" title="Probability density">probability density</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">, provided that we know a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> proportional to the <a href="Probability_density_function" title="Probability density function">density</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> and the values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> can be calculated. The requirement that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> must only be proportional to the density, rather than exactly equal to it, makes the Metropolis–Hastings algorithm particularly useful, because it removes the need to calculate the density's normalization factor, which is often extremely difficult in practice.

The Metropolis–Hastings algorithm generates a sequence of sample values in such a way that, as more and more sample values are produced, the distribution of values more closely approximates the desired distribution. These sample values are produced iteratively in such a way, that the distribution of the next sample depends only on the current sample value, which makes the sequence of samples a <a href="Markov_chain" title="Markov chain">Markov chain</a>. Specifically, at each iteration, the algorithm proposes a candidate for the next sample value based on the current sample value. Then, with some probability, the candidate is either accepted, in which case the candidate value is used in the next iteration, or it is rejected in which case the candidate value is discarded, and the current value is reused in the next iteration. The probability of acceptance is determined by comparing the values of the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> of the current and candidate sample values with respect to the desired distribution.

The method used to propose new candidates is characterized by the probability distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x\mid y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x\mid y)}</annotation>

</semantics>

</math><img src="./0fad3f9abda9015fbce0c1d66a5c21bb630b5197.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.348ex; height:2.843ex;" alt="{\displaystyle g(x\mid y)}" loading="lazy"> (sometimes written <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q(x\mid y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q(x\mid y)}</annotation>

</semantics>

</math><img src="./1d998fe629e757b1140e3db7819b98852f8231fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.07ex; height:2.843ex;" alt="{\displaystyle Q(x\mid y)}" loading="lazy">) of a new proposed sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> given the previous sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">. This is called the proposal density, proposal function, or jumping distribution. A common choice for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x\mid y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x\mid y)}</annotation>

</semantics>

</math><img src="./0fad3f9abda9015fbce0c1d66a5c21bb630b5197.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.348ex; height:2.843ex;" alt="{\displaystyle g(x\mid y)}" loading="lazy"> is a <a href="Gaussian_distribution" class="mw-redirect" title="Gaussian distribution">Gaussian distribution</a> centered at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">, so that points closer to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> are more likely to be visited next, making the sequence of samples into a <a href="Gaussian_random_walk" class="mw-redirect" title="Gaussian random walk">Gaussian random walk</a>. In the original paper by Metropolis et al. (1953), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x\mid y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x\mid y)}</annotation>

</semantics>

</math><img src="./0fad3f9abda9015fbce0c1d66a5c21bb630b5197.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.348ex; height:2.843ex;" alt="{\displaystyle g(x\mid y)}" loading="lazy"> was suggested to be a uniform distribution limited to some maximum distance from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">. More complicated proposal functions are also possible, such as those of <a href="Hamiltonian_Monte_Carlo" title="Hamiltonian Monte Carlo">Hamiltonian Monte Carlo</a>, <a href="Langevin_Monte_Carlo" class="mw-redirect" title="Langevin Monte Carlo">Langevin Monte Carlo</a>, or <a href="Preconditioned_Crank%E2%80%93Nicolson" class="mw-redirect" title="Preconditioned Crank–Nicolson">preconditioned Crank–Nicolson</a>.

For the purpose of illustration, the Metropolis algorithm, a special case of the Metropolis–Hastings algorithm where the proposal function is symmetric, is described below.

<dl><dt>Metropolis algorithm (symmetric proposal distribution)</dt>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> be a function that is proportional to the desired probability density function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy"> (a.k.a. a target distribution)<a href="#cite_note-8">[a]</a>.

<ol><li>Initialization: Choose an arbitrary point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}}</annotation>

</semantics>

</math><img src="./f279a30bc8eabc788f3fe81c9cfb674e72e858db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.156ex; height:2.009ex;" alt="{\displaystyle x_{t}}" loading="lazy"> to be the first observation in the sample and choose a proposal function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x\mid y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x\mid y)}</annotation>

</semantics>

</math><img src="./0fad3f9abda9015fbce0c1d66a5c21bb630b5197.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.348ex; height:2.843ex;" alt="{\displaystyle g(x\mid y)}" loading="lazy">. In this section, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> is assumed to be symmetric; in other words, it must satisfy <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x\mid y)=g(y\mid x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x\mid y)=g(y\mid x)}</annotation>

</semantics>

</math><img src="./060a7816922fe731722075c56c704ff4394e502a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.794ex; height:2.843ex;" alt="{\displaystyle g(x\mid y)=g(y\mid x)}" loading="lazy">.</li>

<li>For each iteration t:

<ul><li>Propose a candidate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> for the next sample by picking from the distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x'\mid x_{t})}">

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x'\mid x_{t})}</annotation>

</semantics>

</math><img src="./17e64ec5812bba0bdf98a21da62ecdebdc2ca692.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.033ex; height:3.009ex;" alt="{\displaystyle g(x'\mid x_{t})}" loading="lazy">.</li>

<li>Calculate the acceptance ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha =f(x')/f(x_{t})}">

<msup>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha =f(x')/f(x_{t})}</annotation>

</semantics>

</math><img src="./610555f6dff744cc1ecddbe53fe9b1cd1f53a9d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.094ex; height:3.009ex;" alt="{\displaystyle \alpha =f(x')/f(x_{t})}" loading="lazy">, which will be used to decide whether to accept or reject the candidate<a href="#cite_note-9">[b]</a>. Because f is proportional to the density of P, we have that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha =f(x')/f(x_{t})=P(x')/P(x_{t})}">

<msup>

</msup>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha =f(x')/f(x_{t})=P(x')/P(x_{t})}</annotation>

</semantics>

</math><img src="./5a324ce2ea357291c9a9000dcf4b7e42c1865721.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.635ex; height:3.009ex;" alt="{\displaystyle \alpha =f(x')/f(x_{t})=P(x')/P(x_{t})}" loading="lazy">.</li>

<li>Accept or reject:

<ul><li>Generate a uniform random number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u\in [0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u\in [0,1]}</annotation>

</semantics>

</math><img src="./5ab4b2bf4a8cda1b335fdb4f789c61285c971034.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.823ex; height:2.843ex;" alt="{\displaystyle u\in [0,1]}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u\leq \alpha }</annotation>

</semantics>

</math><img src="./26157507e219016bec8e55f92d21377b09a1da17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.916ex; height:2.176ex;" alt="{\displaystyle u\leq \alpha }" loading="lazy">, then accept the candidate by setting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t+1}=x'}">

<msub>

</mrow>

</msub>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t+1}=x'}</annotation>

</semantics>

</math><img src="./6c6e996412ae03d02fd2e4fbf6e709c79996701a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.369ex; height:2.843ex;" alt="{\displaystyle x_{t+1}=x'}" loading="lazy">,</li>

<li>If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u>\alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u>\alpha }</annotation>

</semantics>

</math><img src="./853e4acdb3f1bc3a66726b5e0902ff5d70e3d4e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.916ex; height:1.843ex;" alt="{\displaystyle u>\alpha }" loading="lazy">, then reject the candidate and set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t+1}=x_{t}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t+1}=x_{t}}</annotation>

</semantics>

</math><img src="./66dd025c633873e35ab620e7b9d287a121ca06dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.51ex; height:2.009ex;" alt="{\displaystyle x_{t+1}=x_{t}}" loading="lazy"> instead.</li></ul></li></ul></li></ol>

This algorithm proceeds by randomly attempting to move about the sample space, sometimes accepting the moves and sometimes remaining in place. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy"> at specific point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is proportional to the iterations spent on the point by the algorithm. Note that the acceptance ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> indicates how probable the new proposed sample is with respect to the current sample, according to the distribution whose density is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">. If we attempt to move to a point that is more probable than the existing point (i.e. a point in a higher-density region of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy"> corresponding to an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha >1\geq u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha >1\geq u}</annotation>

</semantics>

</math><img src="./6c72f978d3e2b44eeb7bad9165c09b39f90267a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.177ex; height:2.343ex;" alt="{\displaystyle \alpha >1\geq u}" loading="lazy">), we will always accept the move. However, if we attempt to move to a less probable point, we will sometimes reject the move, and the larger the relative drop in probability, the more likely we are to reject the new point. Thus, we will tend to stay in (and return large numbers of samples from) high-density regions of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">, while only occasionally visiting low-density regions. Intuitively, this is why this algorithm works and returns samples that follow the desired distribution with density <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">.

Compared with an algorithm like <a href="Adaptive_rejection_sampling" class="mw-redirect" title="Adaptive rejection sampling">adaptive rejection sampling</a><a href="#cite_note-:0-10">[8]</a> that directly generates independent samples from a distribution, Metropolis–Hastings and other MCMC algorithms have a number of disadvantages:

<ul><li>The samples are <a href="Autocorrelation" title="Autocorrelation">autocorrelated</a>. Even though over the long term they do correctly follow <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">, a set of nearby samples will be correlated with each other and not correctly reflect the distribution. This means that effective sample sizes can be significantly lower than the number of samples actually taken, leading to large errors.</li>

<li>Although the Markov chain eventually converges to the desired distribution, the initial samples may follow a very different distribution, especially if the starting point is in a region of low density. As a result, a burn-in period is typically necessary,<a href="#cite_note-11">[9]</a> where an initial number of samples are thrown away.</li></ul>

On the other hand, most simple <a href="Rejection_sampling" title="Rejection sampling">rejection sampling</a> methods suffer from the "<a href="Curse_of_dimensionality" title="Curse of dimensionality">curse of dimensionality</a>", where the probability of rejection increases exponentially as a function of the number of dimensions. Metropolis–Hastings, along with other MCMC methods, do not have this problem to such a degree, and thus are often the only solutions available when the number of dimensions of the distribution to be sampled is high. As a result, MCMC methods are often the methods of choice for producing samples from <a href="Hierarchical_Bayesian_model" class="mw-redirect" title="Hierarchical Bayesian model">hierarchical Bayesian models</a> and other high-dimensional statistical models used nowadays in many disciplines.

In <a href="Multivariate_distribution" class="mw-redirect" title="Multivariate distribution">multivariate</a> distributions, the classic Metropolis–Hastings algorithm as described above involves choosing a new multi-dimensional sample point. When the number of dimensions is high, finding the suitable jumping distribution to use can be difficult, as the different individual dimensions behave in very different ways, and the jumping width (see above) must be "just right" for all dimensions at once to avoid excessively slow mixing. An alternative approach that often works better in such situations, known as <a href="Gibbs_sampling" title="Gibbs sampling">Gibbs sampling</a>, involves choosing a new sample for each dimension separately from the others, rather than choosing a sample for all dimensions at once. That way, the problem of sampling from potentially high-dimensional space will be reduced to a collection of problems to sample from small dimensionality.<a href="#cite_note-12">[10]</a> This is especially applicable when the multivariate distribution is composed of a set of individual <a href="Random_variable" title="Random variable">random variables</a> in which each variable is conditioned on only a small number of other variables, as is the case in most typical <a href="Hierarchical_Bayesian_model" class="mw-redirect" title="Hierarchical Bayesian model">hierarchical models</a>. The individual variables are then sampled one at a time, with each variable conditioned on the most recent values of all the others. Various algorithms can be used to choose these individual samples, depending on the exact form of the multivariate distribution: some possibilities are the <a href="Adaptive_rejection_sampling" class="mw-redirect" title="Adaptive rejection sampling">adaptive rejection sampling</a> methods,<a href="#cite_note-:0-10">[8]</a> the adaptive rejection Metropolis sampling algorithm,<a href="#cite_note-13">[11]</a> a simple one-dimensional Metropolis–Hastings step, or <a href="Slice_sampling" title="Slice sampling">slice sampling</a>.

<div class="mw-heading mw-heading2"><h2 id="Formal_derivation">Formal derivation</h2></div>

The purpose of the Metropolis–Hastings algorithm is to generate a collection of states according to a desired distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">. To accomplish this, the algorithm uses a <a href="Markov_process" class="mw-redirect" title="Markov process">Markov process</a>, which asymptotically reaches a unique <a href="Markov_chain#Steady-state_analysis_and_limiting_distributions" title="Markov chain">stationary distribution</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)}</annotation>

</semantics>

</math><img src="./5a62d9bf7b2ba03b30a95e7059362cc4b3865123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.471ex; height:2.843ex;" alt="{\displaystyle \pi (x)}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)=P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)=P(x)}</annotation>

</semantics>

</math><img src="./572ca6341d1c9adab806a8b04f9d20aad35678d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.454ex; height:2.843ex;" alt="{\displaystyle \pi (x)=P(x)}" loading="lazy">.<a href="#cite_note-Roberts_Casella-14">[12]</a>

A Markov process is uniquely defined by its transition probabilities <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x'\mid x)}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x'\mid x)}</annotation>

</semantics>

</math><img src="./b2cc256ac50bb45edc073d92ff6fd9273fcd385f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.836ex; height:3.009ex;" alt="{\displaystyle P(x'\mid x)}" loading="lazy">, the probability of transitioning from any given state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> to any other given state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy">. It has a unique stationary distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)}</annotation>

</semantics>

</math><img src="./5a62d9bf7b2ba03b30a95e7059362cc4b3865123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.471ex; height:2.843ex;" alt="{\displaystyle \pi (x)}" loading="lazy"> when the following two conditions are met:<a href="#cite_note-Roberts_Casella-14">[12]</a>

<ol><li>Existence of stationary distribution: there must exist a stationary distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)}</annotation>

</semantics>

</math><img src="./5a62d9bf7b2ba03b30a95e7059362cc4b3865123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.471ex; height:2.843ex;" alt="{\displaystyle \pi (x)}" loading="lazy">. A sufficient but not necessary condition is <a href="Detailed_balance" title="Detailed balance">detailed balance</a>, which requires that each transition <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\to x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\to x'}</annotation>

</semantics>

</math><img src="./5acd2bb16fa2e7ef330ee063fb7a35ccc1bdc5ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.958ex; height:2.509ex;" alt="{\displaystyle x\to x'}" loading="lazy"> is reversible: for every pair of states <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,x'}</annotation>

</semantics>

</math><img src="./868106c4dab7e143519d80dfb0ce9ca91f367330.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:2.843ex;" alt="{\displaystyle x,x'}" loading="lazy">, the probability of being in state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and transitioning to state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> must be equal to the probability of being in state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> and transitioning to state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)P(x'\mid x)=\pi (x')P(x\mid x')}">

<msup>

</msup>

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)P(x'\mid x)=\pi (x')P(x\mid x')}</annotation>

</semantics>

</math><img src="./6d453d82f639104d38358e6870794328841b8f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.397ex; height:3.009ex;" alt="{\displaystyle \pi (x)P(x'\mid x)=\pi (x')P(x\mid x')}" loading="lazy">.</li>

<li>Uniqueness of stationary distribution: the stationary distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)}</annotation>

</semantics>

</math><img src="./5a62d9bf7b2ba03b30a95e7059362cc4b3865123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.471ex; height:2.843ex;" alt="{\displaystyle \pi (x)}" loading="lazy"> must be unique. This is guaranteed by <a href="Markov_Chain" class="mw-redirect" title="Markov Chain">ergodicity</a> of the Markov process, which requires that every state must (1) be aperiodic—the system does not return to the same state at fixed intervals; and (2) be positive recurrent—the expected number of steps for returning to the same state is finite.</li></ol>

The Metropolis–Hastings algorithm involves designing a Markov process (by constructing transition probabilities) that fulfills the two above conditions, such that its stationary distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)}</annotation>

</semantics>

</math><img src="./5a62d9bf7b2ba03b30a95e7059362cc4b3865123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.471ex; height:2.843ex;" alt="{\displaystyle \pi (x)}" loading="lazy"> is chosen to be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">. The derivation of the algorithm starts with the condition of <a href="Detailed_balance" title="Detailed balance">detailed balance</a>:

<msup>

</msup>

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x'\mid x)P(x)=P(x\mid x')P(x'),}</annotation>

</semantics>

</math><img src="./43bb600e271967b155332864f438cc974bd36958.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.871ex; height:3.009ex;" alt="{\displaystyle P(x'\mid x)P(x)=P(x\mid x')P(x'),}" loading="lazy"></dd></dl>

which is re-written as

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

<msup>

</msup>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {P(x'\mid x)}{P(x\mid x')}}={\frac {P(x')}{P(x)}}.}</annotation>

</semantics>

</math><img src="./282cd93a3d68b1ba846de8ddce90f9724816d0b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:19.823ex; height:6.509ex;" alt="{\displaystyle {\frac {P(x'\mid x)}{P(x\mid x')}}={\frac {P(x')}{P(x)}}.}" loading="lazy"></dd></dl>

The approach is to separate the transition in two sub-steps; the proposal and the acceptance-rejection. The proposal distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x'\mid x)}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x'\mid x)}</annotation>

</semantics>

</math><img src="./9a77d4a76664ad2be71b14344068efb8b6943c54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.207ex; height:3.009ex;" alt="{\displaystyle g(x'\mid x)}" loading="lazy"> is the conditional probability of proposing a state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> given <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, and the acceptance distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(x',x)}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(x',x)}</annotation>

</semantics>

</math><img src="./93c634a4e0abfd81947a8ad39ede1cf39b03b2d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.93ex; height:3.009ex;" alt="{\displaystyle A(x',x)}" loading="lazy"> is the probability to accept the proposed state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy">. The transition probability can be written as the product of them:

<msup>

</msup>

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x'\mid x)=g(x'\mid x)A(x',x).}</annotation>

</semantics>

</math><img src="./a81ec496b08bdf3e498b3415d2e47aaaeb932761.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.718ex; height:3.009ex;" alt="{\displaystyle P(x'\mid x)=g(x'\mid x)A(x',x).}" loading="lazy"></dd></dl>

Inserting this relation in the previous equation, we have

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

<msup>

</msup>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

<msup>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {A(x',x)}{A(x,x')}}={\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}.}</annotation>

</semantics>

</math><img src="./faa7ffa48d388245fcb20932c5fb933a8d581637.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:27.96ex; height:6.509ex;" alt="{\displaystyle {\frac {A(x',x)}{A(x,x')}}={\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}.}" loading="lazy"></dd></dl>

The next step in the derivation is to choose an acceptance ratio that fulfills the condition above. One common choice is the Metropolis choice:

<msup>

</msup>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

<msup>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(x',x)=\min \left(1,{\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}\right).}</annotation>

</semantics>

</math><img src="./a9115affde0fa5f2e491c9ffc1ce1bf7899f1984.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:37.391ex; height:6.509ex;" alt="{\displaystyle A(x',x)=\min \left(1,{\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}\right).}" loading="lazy"></dd></dl>

For this Metropolis acceptance ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, either <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(x',x)=1}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(x',x)=1}</annotation>

</semantics>

</math><img src="./25feb60b3c795ccd24cc92e952f1a410b08ce6b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.191ex; height:3.009ex;" alt="{\displaystyle A(x',x)=1}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(x,x')=1}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(x,x')=1}</annotation>

</semantics>

</math><img src="./da0220f0482b04d6da2ad58d66f12f4df118344e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.191ex; height:3.009ex;" alt="{\displaystyle A(x,x')=1}" loading="lazy"> and, either way, the condition is satisfied.

The Metropolis–Hastings algorithm can thus be written as follows:

<ol><li>Initialise

<ol><li>Pick an initial state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation>

</semantics>

</math><img src="./86f21d0e31751534cd6584264ecf864a6aa792cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=0}</annotation>

</semantics>

</math><img src="./43469ec032d858feae5aa87029e22eaaf0109e9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t=0}" loading="lazy">.</li></ol></li>

<li>Iterate

<ol><li>Generate a random candidate state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> according to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x'\mid x_{t})}">

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x'\mid x_{t})}</annotation>

</semantics>

</math><img src="./17e64ec5812bba0bdf98a21da62ecdebdc2ca692.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.033ex; height:3.009ex;" alt="{\displaystyle g(x'\mid x_{t})}" loading="lazy">.</li>

<li>Calculate the acceptance probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)}">

<msup>

</msup>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msup>

</msup>

</mrow>

<mrow>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)}</annotation>

</semantics>

</math><img src="./4c3f782559405b56289d1ad9535bc8a30ffc9c53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:38.15ex; height:6.509ex;" alt="{\displaystyle A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)}" loading="lazy">.</li>

<li>Accept or reject:

<ol><li>generate a uniform random number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u\in [0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u\in [0,1]}</annotation>

</semantics>

</math><img src="./5ab4b2bf4a8cda1b335fdb4f789c61285c971034.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.823ex; height:2.843ex;" alt="{\displaystyle u\in [0,1]}" loading="lazy">;</li>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u\leq A(x',x_{t})}</annotation>

</semantics>

</math><img src="./440ef14b5f0dd49f68a8d9b0e515a9d9a6e3915e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.185ex; height:3.009ex;" alt="{\displaystyle u\leq A(x',x_{t})}" loading="lazy">, then accept the new state and set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t+1}=x'}">

<msub>

</mrow>

</msub>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t+1}=x'}</annotation>

</semantics>

</math><img src="./6c6e996412ae03d02fd2e4fbf6e709c79996701a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.369ex; height:2.843ex;" alt="{\displaystyle x_{t+1}=x'}" loading="lazy">;</li>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u>A(x',x_{t})}</annotation>

</semantics>

</math><img src="./375aeaa99f6d993ea79e257199a5b2279a5e34dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.185ex; height:3.009ex;" alt="{\displaystyle u>A(x',x_{t})}" loading="lazy">, then reject the new state, and copy the old state forward <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t+1}=x_{t}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t+1}=x_{t}}</annotation>

</semantics>

</math><img src="./66dd025c633873e35ab620e7b9d287a121ca06dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.51ex; height:2.009ex;" alt="{\displaystyle x_{t+1}=x_{t}}" loading="lazy">.</li></ol></li>

<li>Increment: set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=t+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=t+1}</annotation>

</semantics>

</math><img src="./01cb12d9cf01ed81c925db967bdf97d7f20f9f42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.781ex; height:2.343ex;" alt="{\displaystyle t=t+1}" loading="lazy">.</li></ol></li></ol>

Provided that specified conditions are met, the empirical distribution of saved states <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0},\ldots ,x_{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0},\ldots ,x_{T}}</annotation>

</semantics>

</math><img src="./3edfd3a9d97db2cd6173a1dfcb90440d784a52c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.281ex; height:2.009ex;" alt="{\displaystyle x_{0},\ldots ,x_{T}}" loading="lazy"> will approach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">. The number of iterations (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">) required to effectively estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy"> depends on the number of factors, including the relationship between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy"> and the proposal distribution and the desired accuracy of estimation.<a href="#cite_note-15">[13]</a> For distribution on discrete state spaces, it has to be of the order of the <a href="Autocorrelation" title="Autocorrelation">autocorrelation</a> time of the Markov process.<a href="#cite_note-Newman_Barkema-16">[14]</a>

It is important to notice that it is not clear, in a general problem, which distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x'\mid x)}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x'\mid x)}</annotation>

</semantics>

</math><img src="./9a77d4a76664ad2be71b14344068efb8b6943c54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.207ex; height:3.009ex;" alt="{\displaystyle g(x'\mid x)}" loading="lazy"> one should use or the number of iterations necessary for proper estimation; both are free parameters of the method, which must be adjusted to the particular problem in hand.

<div class="mw-heading mw-heading2"><h2 id="Use_in_numerical_integration">Use in numerical integration</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Monte_Carlo_integration" title="Monte Carlo integration">Monte Carlo integration</a></div>

A common use of Metropolis–Hastings algorithm is to compute an integral. Specifically, consider a space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega \subset \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega \subset \mathbb {R} }</annotation>

</semantics>

</math><img src="./5e66ab6d255b093f9b592bd1887a745dc304d4d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.455ex; height:2.176ex;" alt="{\displaystyle \Omega \subset \mathbb {R} }" loading="lazy"> and a probability distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy"> over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \Omega }</annotation>

</semantics>

</math><img src="./40de8fa70c126001826d34da2a114349d8476bb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.848ex; height:2.176ex;" alt="{\displaystyle x\in \Omega }" loading="lazy">. Metropolis–Hastings can estimate an integral of the form of

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)=\int _{\Omega }A(x)P(x)\,dx,}</annotation>

</semantics>

</math><img src="./e5a1d0e9b3c02297a873211b2a9e05383395e87f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:24.873ex; height:5.676ex;" alt="{\displaystyle P(E)=\int _{\Omega }A(x)P(x)\,dx,}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(x)}</annotation>

</semantics>

</math><img src="./b078651e6d1a522e8955b73059fbd63e13aec616.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.882ex; height:2.843ex;" alt="{\displaystyle A(x)}" loading="lazy"> is a (measurable) function of interest.

For example, consider a <a href="Statistic" title="Statistic">statistic</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(x)}</annotation>

</semantics>

</math><img src="./e2411ec03b08babee0aa5cbf7a90ba80690a3a0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.915ex; height:2.843ex;" alt="{\displaystyle E(x)}" loading="lazy"> and its probability distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy">, which is a <a href="Marginal_distribution" title="Marginal distribution">marginal distribution</a>. Suppose that the goal is to estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> on the tail of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy">. Formally, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy"> can be written as

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)=\int _{\Omega }P(E\mid x)P(x)\,dx=\int _{\Omega }\delta {\big (}E-E(x){\big )}P(x)\,dx=E{\big (}P(E\mid X){\big )}}</annotation>

</semantics>

</math><img src="./af1b6f21290897e6ba06960a348a174b51dd13ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:70.916ex; height:5.676ex;" alt="{\displaystyle P(E)=\int _{\Omega }P(E\mid x)P(x)\,dx=\int _{\Omega }\delta {\big (}E-E(x){\big )}P(x)\,dx=E{\big (}P(E\mid X){\big )}}" loading="lazy"></dd></dl>

and, thus, estimating <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy"> can be accomplished by estimating the expected value of the <a href="Indicator_function" title="Indicator function">indicator function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{E}(x)\equiv \mathbf {1} _{E}(x)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{E}(x)\equiv \mathbf {1} _{E}(x)}</annotation>

</semantics>

</math><img src="./4768dae34c9a7caf7b0a6403d42423b2ff6dc2ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.432ex; height:2.843ex;" alt="{\displaystyle A_{E}(x)\equiv \mathbf {1} _{E}(x)}" loading="lazy">, which is 1 when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(x)\in [E,E+\Delta E]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(x)\in [E,E+\Delta E]}</annotation>

</semantics>

</math><img src="./a7bce935fdd4fc6a2721d4bdf95832c86c1c1630.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.186ex; height:2.843ex;" alt="{\displaystyle E(x)\in [E,E+\Delta E]}" loading="lazy"> and zero otherwise.

Because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> is on the tail of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy">, the probability to draw a state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(x)}</annotation>

</semantics>

</math><img src="./e2411ec03b08babee0aa5cbf7a90ba80690a3a0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.915ex; height:2.843ex;" alt="{\displaystyle E(x)}" loading="lazy"> on the tail of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy"> is proportional to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy">, which is small by definition. The Metropolis–Hastings algorithm can be used here to sample (rare) states more likely and thus increase the number of samples used to estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(E)}</annotation>

</semantics>

</math><img src="./687fe7f4688af755503fd00e7538f285e2a9954b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.33ex; height:2.843ex;" alt="{\displaystyle P(E)}" loading="lazy"> on the tails. This can be done e.g. by using a sampling distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)}</annotation>

</semantics>

</math><img src="./5a62d9bf7b2ba03b30a95e7059362cc4b3865123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.471ex; height:2.843ex;" alt="{\displaystyle \pi (x)}" loading="lazy"> to favor those states (e.g. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (x)\propto e^{aE}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)\propto e^{aE}}</annotation>

</semantics>

</math><img src="./d89d6e522fd8e6dbf0234b9694b4b8596b31631f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.01ex; height:3.176ex;" alt="{\displaystyle \pi (x)\propto e^{aE}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a>0}</annotation>

</semantics>

</math><img src="./1f34a80ea013edb56e340b19550430a8b6dfd7b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;" alt="{\displaystyle a>0}" loading="lazy">).

<div class="mw-heading mw-heading2"><h2 id="Step-by-step_instructions">Step-by-step instructions</h2></div>

Suppose that the most recent value sampled is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}}</annotation>

</semantics>

</math><img src="./f279a30bc8eabc788f3fe81c9cfb674e72e858db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.156ex; height:2.009ex;" alt="{\displaystyle x_{t}}" loading="lazy">. To follow the Metropolis–Hastings algorithm, we next draw a new proposal state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> with probability density <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x'\mid x_{t})}">

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x'\mid x_{t})}</annotation>

</semantics>

</math><img src="./17e64ec5812bba0bdf98a21da62ecdebdc2ca692.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.033ex; height:3.009ex;" alt="{\displaystyle g(x'\mid x_{t})}" loading="lazy"> and calculate a value

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=a_{1}a_{2},}</annotation>

</semantics>

</math><img src="./b0b301c72f92084a657a956f37ea44450704ef69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.543ex; height:2.009ex;" alt="{\displaystyle a=a_{1}a_{2},}" loading="lazy"></dd></dl>

where

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}={\frac {P(x')}{P(x_{t})}}}</annotation>

</semantics>

</math><img src="./976d444df3033a52a1b559cea37d1ed4477905a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:11.929ex; height:6.509ex;" alt="{\displaystyle a_{1}={\frac {P(x')}{P(x_{t})}}}" loading="lazy"></dd></dl>

is the probability (e.g., Bayesian posterior) ratio between the proposed sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> and the previous sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}}</annotation>

</semantics>

</math><img src="./f279a30bc8eabc788f3fe81c9cfb674e72e858db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.156ex; height:2.009ex;" alt="{\displaystyle x_{t}}" loading="lazy">, and

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msup>

</msup>

</mrow>

<mrow>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{2}={\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}}</annotation>

</semantics>

</math><img src="./9e50c7c355a4faba1891fd5928cc5b43b42ae5de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:15.251ex; height:6.509ex;" alt="{\displaystyle a_{2}={\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}}" loading="lazy"></dd></dl>

is the ratio of the proposal density in two directions (from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}}</annotation>

</semantics>

</math><img src="./f279a30bc8eabc788f3fe81c9cfb674e72e858db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.156ex; height:2.009ex;" alt="{\displaystyle x_{t}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> and conversely).

This is equal to 1 if the proposal density is symmetric.

Then the new state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t+1}}</annotation>

</semantics>

</math><img src="./ef8bcaa338a0582c5fac7993f781cbc57a46e658.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.256ex; height:2.009ex;" alt="{\displaystyle x_{t+1}}" loading="lazy"> is chosen according to the following rules.

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\geq 1{:}}</annotation>

</semantics>

</math><img src="./6f3ceb1beaa92633a94411a186d7e6aef5753a73.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.138ex; height:2.343ex;" alt="{\displaystyle a\geq 1{:}}" loading="lazy">

<msub>

</mrow>

</msub>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t+1}=x',}</annotation>

</semantics>

</math><img src="./6d7ce6caa9233064b27c72eb47d95b225c9ac698.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.016ex; height:2.843ex;" alt="{\displaystyle x_{t+1}=x',}" loading="lazy"></dd></dl></dd>

<dd>else:

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msup>

</msup>

</mtd>

<mtd>

<mtext>with probability </mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mtext>with probability </mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t+1}={\begin{cases}x'&{\text{with probability }}a,\\x_{t}&{\text{with probability }}1-a.\end{cases}}}</annotation>

</semantics>

</math><img src="./9d04b95320ce9f4766593d4930029880ccffdcf2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:37.077ex; height:6.176ex;" alt="{\displaystyle x_{t+1}={\begin{cases}x'&{\text{with probability }}a,\\x_{t}&{\text{with probability }}1-a.\end{cases}}}" loading="lazy"></dd></dl></dd></dl>

The Markov chain is started from an arbitrary initial value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation>

</semantics>

</math><img src="./86f21d0e31751534cd6584264ecf864a6aa792cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}" loading="lazy">, and the algorithm is run for many iterations until this initial state is "forgotten". These samples, which are discarded, are known as burn-in. The remaining set of accepted values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> represent a <a href="Sample_(statistics)" class="mw-redirect" title="Sample (statistics)">sample</a> from the distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">.

The algorithm works best if the proposal density matches the shape of the target distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">, from which direct sampling is difficult, that is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x'\mid x_{t})\approx P(x')}">

<msup>

</msup>

<msub>

</mrow>

</msub>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x'\mid x_{t})\approx P(x')}</annotation>

</semantics>

</math><img src="./215b90fb9682dbe2e948c108748c846abd613410.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.7ex; height:3.009ex;" alt="{\displaystyle g(x'\mid x_{t})\approx P(x')}" loading="lazy">.

If a Gaussian proposal density <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> is used, the variance parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma ^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}}</annotation>

</semantics>

</math><img src="./53a5c55e536acf250c1d3e0f754be5692b843ef5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.385ex; height:2.676ex;" alt="{\displaystyle \sigma ^{2}}" loading="lazy"> has to be tuned during the burn-in period.

This is usually done by calculating the acceptance rate, which is the fraction of proposed samples that is accepted in a window of the last <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> samples.

The desired acceptance rate depends on the target distribution, however it has been shown theoretically that the ideal acceptance rate for a one-dimensional Gaussian distribution is about 50%, decreasing to about 23% for an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-dimensional Gaussian target distribution.<a href="#cite_note-Roberts-17">[15]</a> These guidelines can work well when sampling from sufficiently regular Bayesian posteriors as they often follow a multivariate normal distribution as can be established using the <a href="Bernstein%E2%80%93von_Mises_theorem" title="Bernstein–von Mises theorem">Bernstein–von Mises theorem</a>.<a href="#cite_note-18">[16]</a>

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma ^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}}</annotation>

</semantics>

</math><img src="./53a5c55e536acf250c1d3e0f754be5692b843ef5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.385ex; height:2.676ex;" alt="{\displaystyle \sigma ^{2}}" loading="lazy"> is too small, the chain will mix slowly (i.e., the acceptance rate will be high, but successive samples will move around the space slowly, and the chain will converge only slowly to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy">). On the other hand,

if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma ^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}}</annotation>

</semantics>

</math><img src="./53a5c55e536acf250c1d3e0f754be5692b843ef5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.385ex; height:2.676ex;" alt="{\displaystyle \sigma ^{2}}" loading="lazy"> is too large, the acceptance rate will be very low because the proposals are likely to land in regions of much lower probability density, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}}</annotation>

</semantics>

</math><img src="./bbf42ecda092975c9c69dae84e16182ba5fe2e07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{1}}" loading="lazy"> will be very small, and again the chain will converge very slowly. One typically tunes the proposal distribution so that the algorithms accepts on the order of 30% of all samples – in line with the theoretical estimates mentioned in the previous paragraph.

<div class="mw-heading mw-heading2"><h2 id="Bayesian_Inference">Bayesian Inference</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Bayesian_Inference" class="mw-redirect" title="Bayesian Inference">Bayesian Inference</a></div>

MCMC can be used to draw samples from the <a href="Posterior_distribution" class="mw-redirect" title="Posterior distribution">posterior distribution</a> of a statistical model.

The acceptance probability is given by:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{acc}(\theta _{i}\to \theta ^{*})=\min \left(1,{\frac {{\mathcal {L}}(y|\theta ^{*})P(\theta ^{*})}{{\mathcal {L}}(y|\theta _{i})P(\theta _{i})}}{\frac {Q(\theta _{i}|\theta ^{*})}{Q(\theta ^{*}|\theta _{i})}}\right),}</annotation>

</semantics>

</math><img src="./994636aa96438143b13da7f7efca6d0427634034.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:50.55ex; height:6.509ex;" alt="{\displaystyle P_{acc}(\theta _{i}\to \theta ^{*})=\min \left(1,{\frac {{\mathcal {L}}(y|\theta ^{*})P(\theta ^{*})}{{\mathcal {L}}(y|\theta _{i})P(\theta _{i})}}{\frac {Q(\theta _{i}|\theta ^{*})}{Q(\theta ^{*}|\theta _{i})}}\right),}" loading="lazy">

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {L}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {L}}}</annotation>

</semantics>

</math><img src="./9027196ecb178d598958555ea01c43157d83597c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.604ex; height:2.176ex;" alt="{\displaystyle {\mathcal {L}}}" loading="lazy"> is the <a href="Likelihood" class="mw-redirect" title="Likelihood">likelihood</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(\theta )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(\theta )}</annotation>

</semantics>

</math><img src="./543ecac78af032493892f6608bff05542e961edb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.645ex; height:2.843ex;" alt="{\displaystyle P(\theta )}" loading="lazy"> the prior probability density and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"> the (conditional) proposal probability.

<ul><li><a href="Genetic_algorithm" title="Genetic algorithm">Genetic algorithms</a></li>

<li><a href="Mean-field_particle_methods" title="Mean-field particle methods">Mean-field particle methods</a></li>

<li><a href="Metropolis_light_transport" title="Metropolis light transport">Metropolis light transport</a></li>

<li><a href="Multiple-try_Metropolis" title="Multiple-try Metropolis">Multiple-try Metropolis</a></li>

<li><a href="Parallel_tempering" title="Parallel tempering">Parallel tempering</a></li>

<li><a href="Particle_filter" title="Particle filter">Sequential Monte Carlo</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKalosWhitlock1986" class="citation book cs1">Kalos, Malvin H.; Whitlock, Paula A. (1986). Monte Carlo Methods Volume I: Basics. New York: Wiley. pp. 78–88.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFTierney1994" class="citation journal cs1">Tierney, Luke (1994). <a rel="nofollow" class="external text" href="https://projecteuclid.org/journals/annals-of-statistics/volume-22/issue-4/Markov-Chains-for-Exploring-Posterior-Distributions/10.1214/aos/1176325750.full">"Markov chains for exploring posterior distributions"</a>. The Annals of Statistics. 22 (4): 1701–1762. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faos%2F1176325750">10.1214/aos/1176325750</a>.</cite>

</li>

<li id="cite_note-Hastings-3"><a href="#cite_ref-Hastings_3-0">^</a> <cite id="CITEREFHastings1970" class="citation journal cs1">Hastings, W.K. (1970). "Monte Carlo Sampling Methods Using Markov Chains and Their Applications". <a href="Biometrika" title="Biometrika">Biometrika</a>. 57 (1): 97–109. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1970Bimka..57...97H">1970Bimka..57...97H</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fbiomet%2F57.1.97">10.1093/biomet/57.1.97</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2334940">2334940</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0219.65008">0219.65008</a>.</cite>

</li>

<li id="cite_note-Rosenbluth-4"><a href="#cite_ref-Rosenbluth_4-0">^</a> <cite id="CITEREFM.N._Rosenbluth2003" class="citation journal cs1">M.N. Rosenbluth (2003). "Genesis of the Monte Carlo Algorithm for Statistical Mechanics". <a href="AIP_Conference_Proceedings" title="AIP Conference Proceedings">AIP Conference Proceedings</a>. 690: 22–30. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2003AIPC..690...22R">2003AIPC..690...22R</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1063%2F1.1632112">10.1063/1.1632112</a>.</cite>

</li>

<li id="cite_note-Gubernatis-5"><a href="#cite_ref-Gubernatis_5-0">^</a> <cite id="CITEREFJ.E._Gubernatis2005" class="citation journal cs1">J.E. Gubernatis (2005). <a rel="nofollow" class="external text" href="https://zenodo.org/record/1231899">"Marshall Rosenbluth and the Metropolis Algorithm"</a>. <a href="Physics_of_Plasmas" title="Physics of Plasmas">Physics of Plasmas</a>. 12 (5): 057303. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2005PhPl...12e7303G">2005PhPl...12e7303G</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1063%2F1.1887186">10.1063/1.1887186</a>.</cite>

</li>

<li id="cite_note-Teller-6"><a href="#cite_ref-Teller_6-0">^</a> Teller, Edward. Memoirs: A Twentieth-Century Journey in Science and Politics. <a href="Perseus_Publishing" class="mw-redirect" title="Perseus Publishing">Perseus Publishing</a>, 2001, p. 328

</li>

<li id="cite_note-Barth-7"><a href="#cite_ref-Barth_7-0">^</a> Rosenbluth, Marshall. <a rel="nofollow" class="external text" href="https://www.aip.org/history-programs/niels-bohr-library/oral-histories/28636-1">"Oral History Transcript"</a>. American Institute of Physics

</li>

<li id="cite_note-:0-10">^ <a href="#cite_ref-:0_10-0">a</a> <a href="#cite_ref-:0_10-1">b</a> <cite id="CITEREFGilksWild1992" class="citation journal cs1">Gilks, W. R.; Wild, P. (1992-01-01). "Adaptive Rejection Sampling for Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 41 (2): 337–348. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2347565">10.2307/2347565</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2347565">2347565</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite class="citation book cs1">Bayesian data analysis. Gelman, Andrew (2nd ed.). Boca Raton, Fla.: Chapman & Hall / CRC. 2004. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1584883883</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/51991499">51991499</a>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: others (link)

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFLee2021" class="citation journal cs1">Lee, Se Yoon (2021). "Gibbs sampler and coordinate ascent variational inference: A set-theoretical review". Communications in Statistics - Theory and Methods. 51 (6): 1549–1568. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2008.01006">2008.01006</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F03610926.2021.1921214">10.1080/03610926.2021.1921214</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:220935477">220935477</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFGilksBestTan1995" class="citation journal cs1">Gilks, W. R.; <a href="Nicky_Best" title="Nicky Best">Best, N. G.</a>; Tan, K. K. C. (1995-01-01). "Adaptive Rejection Metropolis Sampling within Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2986138">10.2307/2986138</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2986138">2986138</a>.</cite>

</li>

<li id="cite_note-Roberts_Casella-14">^ <a href="#cite_ref-Roberts_Casella_14-0">a</a> <a href="#cite_ref-Roberts_Casella_14-1">b</a> <cite id="CITEREFRobertCasella2004" class="citation book cs1">Robert, Christian; Casella, George (2004). <a rel="nofollow" class="external text" href="https://archive.org/details/springer_10.1007-978-1-4757-4145-2">Monte Carlo Statistical Methods</a>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0387212395</bdi>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> Raftery, Adrian E., and Steven Lewis. "How Many Iterations in the Gibbs Sampler?" In Bayesian Statistics 4. 1992.

</li>

<li id="cite_note-Newman_Barkema-16"><a href="#cite_ref-Newman_Barkema_16-0">^</a> <cite id="CITEREFNewmanBarkema1999" class="citation book cs1">Newman, M. E. J.; Barkema, G. T. (1999). Monte Carlo Methods in Statistical Physics. USA: Oxford University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0198517979</bdi>.</cite>

</li>

<li id="cite_note-Roberts-17"><a href="#cite_ref-Roberts_17-0">^</a> <cite id="CITEREFRobertsGelmanGilks1997" class="citation journal cs1">Roberts, G.O.; Gelman, A.; Gilks, W.R. (1997). <a rel="nofollow" class="external text" href="http://www.stat.columbia.edu/~gelman/research/published/theory7.ps">"Weak convergence and optimal scaling of random walk Metropolis algorithms"</a>. <a href="Ann._Appl._Probab." class="mw-redirect" title="Ann. Appl. Probab.">Ann. Appl. Probab.</a> 7 (1): 110–120. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.717.2582">10.1.1.717.2582</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faoap%2F1034625254">10.1214/aoap/1034625254</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFSchmonGagnon2022" class="citation journal cs1">Schmon, Sebastian M.; Gagnon, Philippe (2022-04-15). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8924149">"Optimal scaling of random walk Metropolis algorithms using Bayesian large-sample asymptotics"</a>. Statistics and Computing. 32 (2): 28. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs11222-022-10080-8">10.1007/s11222-022-10080-8</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0960-3174">0960-3174</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8924149">8924149</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/35310543">35310543</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> In the original paper by Metropolis et al. (1953), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> was taken to be the <a href="Boltzmann_distribution" title="Boltzmann distribution">Boltzmann distribution</a> as the specific application considered was <a href="Monte_Carlo_integration" title="Monte Carlo integration">Monte Carlo integration</a> of <a href="Equation_of_state" title="Equation of state">equations of state</a> in <a href="Physical_chemistry" title="Physical chemistry">physical chemistry</a>; the extension by Hastings generalized to an arbitrary distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> In the original paper by Metropolis et al. (1953), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> was actually the <a href="Boltzmann_distribution" title="Boltzmann distribution">Boltzmann distribution</a>, as it was applied to physical systems in the context of <a href="Statistical_mechanics" title="Statistical mechanics">statistical mechanics</a> (e.g., a maximal-entropy distribution of microstates for a given temperature at thermal equilibrium). Consequently, the acceptance ratio was itself an exponential of the difference in the parameters of the numerator and denominator of this ratio.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><a href="Bernd_A._Berg" class="mw-redirect" title="Bernd A. Berg">Bernd A. Berg</a>. Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Singapore, <a href="World_Scientific" title="World Scientific">World Scientific</a>, 2004.</li>

<li>Chib, Siddhartha; Greenberg, Edward (1995). <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2684568">"Understanding the Metropolis–Hastings Algorithm"</a>. <a href="The_American_Statistician" title="The American Statistician">The American Statistician</a>, 49(4), 327–335.</li>

<li><a rel="nofollow" class="external text" href="http://www.tandfonline.com/doi/abs/10.1080/03610918.2013.777455#.VOk8J1PF9_c">David D. L. Minh and Do Le Minh. "Understanding the Hastings Algorithm." Communications in Statistics - Simulation and Computation, 44:2 332–349, 2015</a></li>

<li>Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, <a href="John_Wiley_%26_Sons" class="mw-redirect" title="John Wiley & Sons">John Wiley & Sons</a> <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-470-04609-0</bdi></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-09" href="https://en.wikipedia.org/wiki/?title=Metropolis%E2%80%93Hastings_algorithm&oldid=1279572778">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>